home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / math / differ.zip / PARSER.C < prev    next >
C/C++ Source or Header  |  1996-02-11  |  11KB  |  461 lines
  1. #include "differ.h"
  2.  
  3. #define fnsym  '#'
  4. #define opsym  '$'
  5. #define xsym   'x'
  6. #define numsym '£'
  7. #define consym '@'
  8. #define lbrac  '('
  9. #define rbrac  ')'
  10. #define fnend 1
  11.  
  12. logical parsefailed;
  13.  
  14. /*
  15.   heres the list of supported functions
  16. */
  17.  
  18. struct sfuncs
  19. { char *name;
  20.   functions command;
  21. } funcs[] =
  22. {  {"exp",EXP},
  23.    {"sinh",SINH},
  24.    {"sin",SIN},
  25.    {"ln",LN},
  26.    {"tanh",TANH},
  27.    {"tan",TAN},
  28.    {"cosech",COSECH},
  29.    {"cosec",COSEC},
  30.    {"coth",COTH},
  31.    {"cot",COT},
  32.    {"cosh",COSH},
  33.    {"cos",COS},
  34.    {"sech",SECH},
  35.    {"sec",SEC},
  36.    {"arcsinh",ARCSINH},
  37.    {"arcsin",ARCSIN},
  38.    {"arccosh",ARCCOSH},
  39.    {"arccos",ARCCOS},
  40.    {"arctanh",ARCTANH},
  41.    {"arctan",ARCTAN},
  42.    {NULL,UNDEF_FUNC}
  43. };
  44.  
  45. /*
  46.    Heres the list of supported operators. Note that although unitary minus
  47.    does not appear in the list it is supported separately in the routines.
  48. */
  49.  
  50. struct sops
  51. { char *name;
  52.   functions command;
  53. } ops[] =
  54. {  {"*",TIMES},
  55.    {"/",DIVIDE},
  56.    {"+",PLUS},
  57.    {"-",MINUS},
  58.    {"^",POWER},
  59.    {NULL,UNDEF_OP}
  60. };
  61.  
  62. /*
  63.   This function takes the input, looks for functions and replaces them
  64.   with markers prior to the parse.
  65. */
  66.  
  67. logical reducefnstosymbols(char *buff)
  68. { int newbufptr=0,
  69.     oldbufptr=0,
  70.     fncounter;
  71.   char tempbuff[MAXINPLINELEN*2];
  72.   logical found;
  73.   while(buff[oldbufptr])
  74.   { fncounter=0;
  75.     found=FALSE;
  76.     if(buff[oldbufptr]==fnsym) return FALSE;
  77.     while(funcs[fncounter].name!=NULL)
  78.     { if(!strnicmp(funcs[fncounter].name,&buff[oldbufptr],strlen(funcs[fncounter].name)))
  79.     { found=TRUE;
  80.       break;
  81.     }
  82.     fncounter++;
  83.     }
  84.     if(found)
  85.     { tempbuff[newbufptr++]=fnsym;
  86.     tempbuff[newbufptr++]=funcs[fncounter].command;
  87.     oldbufptr+=strlen(funcs[fncounter].name);
  88.     }
  89.     else
  90.     tempbuff[newbufptr++]=buff[oldbufptr++];
  91.   }
  92.   tempbuff[newbufptr]=0;
  93.   strcpy(buff,tempbuff);
  94.   return TRUE;
  95. }
  96.  
  97. /*
  98.    This function identifies operators and marks them. It also identifies
  99.    unitary minus.
  100. */
  101.  
  102. logical reduceopstosymbols(char *buff)
  103. { int newbufptr=0,
  104.     oldbufptr=0,
  105.     opcounter;
  106.   char lastchar=0;
  107.   char tempbuff[MAXINPLINELEN*2];
  108.   logical found;
  109.   while(buff[oldbufptr])
  110.   { opcounter=0;
  111.     found=FALSE;
  112.     if(buff[oldbufptr]==opsym) return FALSE;
  113.     while(ops[opcounter].name!=NULL)
  114.     { if(!strnicmp(ops[opcounter].name,&buff[oldbufptr],strlen(ops[opcounter].name)))
  115.     { found=TRUE;
  116.       break;
  117.     }
  118.     opcounter++;
  119.     }
  120.     if(found)
  121.     { tempbuff[newbufptr++]=opsym;
  122.     if(((!lastchar)||(lastchar==lbrac))&&(ops[opcounter].command==MINUS))
  123.       tempbuff[newbufptr++]=UMINUS;
  124.     else
  125.       tempbuff[newbufptr++]=ops[opcounter].command;
  126.     oldbufptr+=strlen(ops[opcounter].name);
  127.     }
  128.     else
  129.     { if(buff[oldbufptr]!=' ')lastchar=buff[oldbufptr];
  130.     tempbuff[newbufptr++]=buff[oldbufptr++];
  131.     }
  132.   }
  133.   tempbuff[newbufptr]=0;
  134.   strcpy(buff,tempbuff);
  135.   return TRUE;
  136. }
  137.  
  138. /*
  139.    This function marks any constants.
  140. */
  141.  
  142. logical findconsts(char *buff)
  143. { int newbufptr=0,
  144.     oldbufptr=0;
  145.   char nextch;
  146.   char tempbuff[MAXINPLINELEN*2];
  147.   while(buff[oldbufptr])
  148.   { nextch=buff[oldbufptr];
  149.     if((nextch==consym)||(nextch==numsym))return FALSE;
  150.     if((isdigit(nextch))||(nextch=='.'))
  151.     { tempbuff[newbufptr++]=numsym;
  152.     while((isdigit(nextch))||(nextch=='.'))
  153.     { tempbuff[newbufptr++]=buff[oldbufptr++];
  154.       nextch=buff[oldbufptr];
  155.     }
  156.     }
  157.     else if((isalpha(nextch))&&(nextch!=xsym))
  158.     { tempbuff[newbufptr++]=consym;
  159.     tempbuff[newbufptr++]=buff[oldbufptr++];
  160.     }
  161.     else
  162.     tempbuff[newbufptr++]=buff[oldbufptr++];
  163.   }
  164.   tempbuff[newbufptr]=0;
  165.   strcpy(buff,tempbuff);
  166.   return TRUE;
  167. }
  168.  
  169. /*
  170.    This is a useful routine. It allocates memory for an item in an expression
  171.    and initialises it.
  172. */
  173.  
  174. struct expression *newtree(void)
  175. { struct expression *allocated;
  176.   if((allocated=(struct expression *)malloc(sizeof(struct expression)))==NULL)
  177.   { printf("Unable to allocate enough memory\n\r");
  178.     exit(1);
  179.   }
  180.   allocated->lval=NULL;
  181.   allocated->rval=NULL;
  182.   return allocated;
  183. }
  184.  
  185. /*
  186.    Here is our expression parser. It is recursive and returns a pointer
  187.    to a tree containing the expression.
  188. */
  189.  
  190. struct expression *parseexpr(char **buff,char endchar)
  191. { struct expression *tree=NULL,
  192.               *temptree,
  193.               *rectree,
  194.               *restree;
  195.   operators optype;
  196.   while(**buff)
  197.   { switch(**buff)
  198.     { case ' ':  (*buff)++;
  199.              break;
  200.     case lbrac:(*buff)++;
  201.              if(tree!=NULL)
  202.              { parsefailed=TRUE;
  203.              printf("Misplaced '('\n\r");
  204.              return tree;
  205.              }
  206.              tree=parseexpr(buff,rbrac);
  207.              temptree=newtree();
  208.              temptree->rval=tree;
  209.              temptree->exptype=OPERATOR;
  210.              temptree->expval.op=BRACKET;
  211.              tree=temptree;
  212.              break;
  213.     case rbrac:if(endchar==fnend) return tree;
  214.              (*buff)++;
  215.              if(tree==NULL)
  216.              { parsefailed=TRUE;
  217.              printf("No expression in brackets\n\r");
  218.              return tree;
  219.              }
  220.              if(endchar!=rbrac)
  221.              { parsefailed=TRUE;
  222.              printf("Misplaced ')'\n\r");
  223.              return tree;
  224.              }
  225.              return tree;
  226.     case xsym: (*buff)++;
  227.              if(tree!=NULL)
  228.              { parsefailed=TRUE;
  229.              printf("Improper expression\n\r");
  230.              return tree;
  231.              }
  232.              tree=newtree();
  233.              tree->exptype=X;
  234.              break;
  235.     case opsym:if(endchar==fnend)return tree;
  236.              (*buff)++;
  237.              optype=(**buff);
  238.              (*buff)++;
  239.              if((tree==NULL)&&(optype!=UMINUS))
  240.              { parsefailed=TRUE;
  241.              printf("Invalid syntax - missing L-Value\n\r");
  242.              return tree;
  243.              }
  244.              temptree=parseexpr(buff,endchar);
  245.              if(temptree==NULL)
  246.              { parsefailed=TRUE;
  247.              printf("Operator with no R-Value\n\r");
  248.              return tree;
  249.              }
  250.              if((temptree->exptype==OPERATOR)&&(optype>=temptree->expval.op))
  251.              { rectree=temptree;
  252.              while((rectree->lval->exptype==OPERATOR)&&(optype>=rectree->lval->expval.op))
  253.                rectree=rectree->lval;
  254.              restree=newtree();
  255.              restree->exptype=OPERATOR;
  256.              restree->expval.op=optype;
  257.              restree->lval=tree;
  258.              restree->rval=rectree->lval;
  259.              rectree->lval=restree;
  260.              tree=temptree;
  261.              }
  262.              else
  263.              { restree=newtree();
  264.              restree->exptype=OPERATOR;
  265.              restree->expval.op=optype;
  266.              restree->lval=tree;
  267.              restree->rval=temptree;
  268.              tree=restree;
  269.              }
  270.              if(endchar) return tree;
  271.              break;
  272.     case fnsym:(*buff)++;
  273.              optype=(**buff);
  274.              (*buff)++;
  275.              if(tree!=NULL)
  276.              { parsefailed=TRUE;
  277.              printf("Invalid syntax - missing operator\n\r");
  278.              return tree;
  279.              }
  280.              temptree=parseexpr(buff,fnend);
  281.              if(temptree==NULL)
  282.              { parsefailed=TRUE;
  283.              printf("Function with no R-Value\n\r");
  284.              return tree;
  285.              }
  286.              tree=newtree();
  287.              tree->exptype=FUNCTION;
  288.              tree->expval.fn=optype;
  289.              tree->rval=temptree;
  290.              break;
  291.     case numsym:(*buff)++;
  292.              if(tree!=NULL)
  293.              { parsefailed=TRUE;
  294.              printf("Improper expression\n\r");
  295.              return tree;
  296.              }
  297.              tree=newtree();
  298.              tree->exptype=VALUE;
  299.              tree->cval=(float)strtod(*buff,buff);
  300.              break;
  301.     case consym:(*buff)++;
  302.              optype=(**buff);
  303.              (*buff)++;
  304.              if(tree!=NULL)
  305.              { parsefailed=TRUE;
  306.              printf("Improper expression\n\r");
  307.              return tree;
  308.              }
  309.              tree=newtree();
  310.              tree->exptype=CONSTANT;
  311.              tree->expval.co=optype;
  312.              break;
  313.     default:   parsefailed=TRUE;
  314.              printf("Unknown symbol : %c",**buff);
  315.              return tree;
  316.     }
  317.   }
  318.   if(endchar==rbrac)
  319.   { parsefailed=TRUE;
  320.     printf("Expression incomplete\n\r");
  321.     return tree;
  322.   }
  323.   return tree;
  324. }
  325.  
  326. /*
  327.    This function removes any bracket pointers which are in the expression.
  328.    Strange results happen if you don't put the bracket notes in, but we
  329.    don't need them afterwards.
  330. */
  331.  
  332. struct expression *removebrackets(struct expression *expr)
  333. { struct expression *exprptr;
  334.   if(expr==NULL) return NULL;
  335.   if(expr->lval!=NULL)expr->lval=removebrackets(expr->lval);
  336.   if(expr->rval!=NULL)expr->rval=removebrackets(expr->rval);
  337.   if(expr->exptype==OPERATOR)
  338.     if(expr->expval.op==BRACKET)
  339.     { exprptr=expr->rval;
  340.     free(expr);
  341.     return exprptr;
  342.     }
  343.   return expr;
  344. }
  345.  
  346. /*
  347.    This just calls all the other functions and checks the results.
  348.    Error indications could be better..
  349. */
  350.  
  351. struct expression *parser(char *buff)
  352. { struct expression *expr;
  353.   if(!reducefnstosymbols(buff))
  354.   { printf("Syntax error\n\r");
  355.     return NULL;
  356.   }
  357.   if(!reduceopstosymbols(buff))
  358.   { printf("Syntax error\n\r");
  359.     return NULL;
  360.   }
  361.   if(!findconsts(buff))
  362.   { printf("Syntax error\n\r");
  363.     return NULL;
  364.   }
  365.   parsefailed=FALSE;
  366.   expr=parseexpr(&buff,0);
  367.   if(parsefailed)
  368.   { freetree(expr);
  369.     return NULL;
  370.   }
  371.   if(buff[0])
  372.   { printf("Syntax error\n\r");
  373.     return NULL;
  374.   }
  375.   expr=removebrackets(expr);
  376.   return expr;
  377. }
  378.  
  379. /*
  380.    This routine prints the expression out. I have tried to remove the
  381.    printing of as many extraneous brackets as possible, this was after
  382.    looking at expressions like ((a)*((x)^(2))) for too long. Its quite
  383.    good now though.
  384. */
  385.  
  386. void printout(struct expression *expr)
  387. { int tval=0;
  388.   operators op1,op2;
  389.   if(expr==NULL) return;
  390.   switch(expr->exptype)
  391.   { case OPERATOR:   if(expr->expval.op!=UMINUS)
  392.                  if(expr->lval->exptype==OPERATOR)
  393.                  if((op1=expr->lval->expval.op)<=(op2=expr->expval.op))
  394.                  { if(!((op1==op2)&&((op1==PLUS)||(op2==TIMES))))
  395.                    { printf("(");
  396.                      printout(expr->lval);
  397.                      printf(")");
  398.                    }
  399.                    else printout(expr->lval);
  400.                  }
  401.                  else printout(expr->lval);
  402.                  else printout(expr->lval);
  403.                switch(expr->expval.op)
  404.                { case PLUS:    printf("+");
  405.                          break;
  406.                  case MINUS:   printf("-");
  407.                          break;
  408.                  case DIVIDE:  printf("/");
  409.                          break;
  410.                  case TIMES:   printf("*");
  411.                          break;
  412.                  case POWER:   printf("^");
  413.                          break;
  414.                  case UMINUS:  printf("-");
  415.                          if(expr->rval->exptype==OPERATOR)
  416.                            if((expr->rval->expval.op==PLUS)||
  417.                             (expr->rval->expval.op==MINUS))
  418.                            { printf("(");
  419.                              printout(expr->rval);
  420.                              printf(")");
  421.                              return;
  422.                            }
  423.                          printout(expr->rval);
  424.                          return;
  425.                  case UNDEF_OP:
  426.                  default:      printf("\n\rInternal error:Undefined operation\n\r");
  427.                          return;
  428.                }
  429.                if(expr->rval->exptype==OPERATOR)
  430.                  if((op1=expr->rval->expval.op)<=(op2=expr->expval.op))
  431.                  { if(!((op1==op2)&&((op1==PLUS)||(op2==TIMES))))
  432.                  { printf("(");
  433.                    printout(expr->rval);
  434.                    printf(")");
  435.                  }
  436.                  else printout(expr->rval);
  437.                  }
  438.                  else printout(expr->rval);
  439.                else printout(expr->rval);
  440.                return;
  441.     case VALUE:      printf("%g",expr->cval);
  442.                return;
  443.     case X:          printf("x");
  444.                return;
  445.     case CONSTANT:   printf("%c",expr->expval.co);
  446.                return;
  447.     case FUNCTION:   while((expr->expval.fn!=funcs[tval].command)&&
  448.                   (funcs[tval].command!=UNDEF_FUNC))tval++;
  449.                if (funcs[tval].name==NULL)
  450.                {  printf("\n\rInternal error:Undefined function\n\r");
  451.                 return;
  452.                }
  453.                printf("%s(",funcs[tval].name);
  454.                printout(expr->rval);
  455.                printf(")");
  456.                return;
  457.     case UNDEF_ETYPE:
  458.     default:         printf("\n\rInternal error:Undefined type\n\r");
  459.                break;
  460.   }
  461. }